

//3026.最大好子数组和
class Solution {
public:
    long long maximumSubarraySum(vector<int>& nums, int k) {
        //求子数组的最大和,考虑使用前缀和
        //此题有前提条件：子数组第一个元素和最后一个差的绝对值为k
        //所以哈希表就要记录每个位置的值,以及该值前面的子数组之和
        //如果哈希表中出现重复的,优先选择前缀和更小的,因为要保证子数组和最大

        int n = nums.size();
        long long sum = 0 ,ret = LLONG_MIN;   //初始化为long long的最小值,因为返回值是long long类型的
        unordered_map<int,long long> m;   
        for(int i = 0; i < n ;i++)
        {
            sum += nums[i];
            int a = nums[i] - k , b = nums[i] + k;      //找差值的绝对值是k的数
            if(m.count(a)) ret = max(ret,sum - m[a]);
            if(m.count(b)) ret = max(ret,sum - m[b]);

            if(!m.count(nums[i])) m[nums[i]] = sum-nums[i]; //如果没有该和,加入
            else m[nums[i]] = min(m[nums[i]] ,sum-nums[i]); //如果有,比较,保留前缀和小的哪一个
        }
        return ret==LLONG_MIN?0:ret;
    }
};